package pers.vic.basics.leetcode;

import java.util.Arrays;

/**
 * @author Vic.xu
 * @description:4. 寻找两个正序数组的中位数
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
 * <p>
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 * @date: 2020/10/29  11:00
 */
public class J0004_H_FindMedianSortedArrays {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        //求出中间数
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        //两个数组合起来的长度是不是偶数
        boolean isEven = len % 2 == 0;
        int left = 0;
        int right = 0;
        if (isEven) {
            right = len / 2;
            left = right - 1;
        } else {
            right = left = len / 2;
        }
        int[] midArr = new int[2];
        int i = 0, j = 0, k = 0;
        while (k <= right) {
            int val = 0;
            boolean arriveLeft = k == left;
            boolean arriveRight = k == right;
            if (i < len1 && j < len2) {
                if (nums1[i] < nums2[j]) {
                    val = nums1[i];
                    i++;
                } else {
                    val = nums2[j];
                    j++;
                }
            } else if (i < len1 && j >= len2) {
                val = nums1[i];
                i++;
            } else if (j < len2 && i >= len1) {
                val = nums2[j];
                j++;
            }
            if (arriveLeft) {
                midArr[0] = val;
            }
            if (arriveRight) {
                midArr[1] = val;
                break;
            }
            k++;
        }
        return (midArr[0] + midArr[1]) / 2.0;
    }


    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int[] arr = mergeOrderedArrays(nums1, nums2);
        int len = arr.length;
        if (len % 2 == 0) {
            return (arr[len / 2] + arr[len / 2 - 1]) / 2.000000;
        } else {
            return arr[len / 2] / 1.000000;
        }
    }


    public static int[] mergeOrderedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;
        int len = len1 + len2;
        int[] arr = new int[len];

        int i = 0, j = 0, k = 0;
        while (k < len) {
            if (i < len1 && j < len2) {
                if (nums1[i] < nums2[j]) {
                    arr[k++] = nums1[i++];
                } else {
                    arr[k++] = nums2[j++];
                }
            } else if (i < len1 && j >= len2) {
                arr[k++] = nums1[i++];
            } else if (j < len2 && i >= len1) {
                arr[k++] = nums2[j++];
            }
        }

        return arr;
    }

    public static void main(String[] args) {
        System.out.println("123");
        int[] arr1 = {1, 3};
        int[] arr2 = {2};
        int[] arr = mergeOrderedArrays(arr1, arr2);
        System.out.println(Arrays.toString(arr));
        System.out.println(findMedianSortedArrays2(arr1, arr2));
        System.out.println(findMedianSortedArrays(arr1, arr2));


    }
}
